package class_1;

/**
 * 在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和.
 * 数组:1 3 4 2 5
 * 1:左边无元素， 因此算出其和为0.
 * 3：左边有元素1， 因此其和为1.
 * 4：左边有元素1，3满足， 因此其和为1+3=4.
 * 2:左边有元素1满足， 因此其和为1.
 * 5:左边有元素1，3，4，2满足， 因此其和为10
 * 所以，数组的小和为0+1+4+1+10 = 16.
 */
public class Coding_smallSum {
	/**
	 * 暴力算法
	 * @param arr: 数组
	 * @return 数组的小和
	 */
	public static int smallSum1(int[] arr) {
		int sum = 0;
		for(int i=0, asum;i<arr.length;i++) {
			asum = 0;
			for(int j=0;j<i;j++) {
				//这里严格不取等。
				if(arr[j]<arr[i]) {
					asum += arr[j];
				}
			}
			sum += asum;
		}
		return sum;
	}
	
	public static void main(String[] args) {
		int[] arr = {1,3,4,2,5};
		int[] arr2 = {4,2,7,7,1,8,3,5};
		System.out.println("(暴力解法)小和为:"+smallSum1(arr));
		System.out.println("(暴力解法)小和为:"+smallSum1(arr2));
	}
}
